package MergeSort;

import java.util.Arrays;

public class InsertionSort {
    private InsertionSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){

        for(int i = 0; i < arr.length ; i++) {
//            for (int j = i; j - 1 >= 0; j--)
//                if (arr[j].compareTo(arr[j - 1]) < 0)
//                    swap(arr, j, j - 1);
//                else break;

            for(int j = i; j - 1 >=0 && arr[j].compareTo(arr[j-1]) < 0; j--){
                swap(arr, j, j - 1);
            }
        }
    }

    public static <E extends Comparable<E>> void sort2(E[] arr){
        for(int i = 0; i < arr.length; i++){
            E t = arr[i];
            int j;
            for(j = i; j - 1 >= 0 && t.compareTo(arr[j-1]) < 0; j--){
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }

    // 在归并排序中使用
    public static <E extends Comparable<E>> void sort2_merge(E[] arr, int l, int r){
        for(int i = l; i <= r; i++){
            E t = arr[i];
            int j;
            for(j = i; j - 1 >= l && t.compareTo(arr[j-1]) < 0; j--){
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }

    private static <E> void swap(E[] arr, int i, int j){
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;

    }

    public static void main(String[] args){

        // 随机数组的使用
        int[] dataSize = {10000, 100000};
        for(int n:dataSize) {

            System.out.println("Random Array : ");
            Integer[] arr2 = ArrayGenerator.generateRandomArray(n, n);
            Integer[] arr3 = Arrays.copyOf(arr2, arr2.length);
            SortingHelper.sortTest("InsertionSort2", arr2);
            SortingHelper.sortTest("SelectionSort", arr3);

            System.out.println("Ordered Array : ");
            arr2 = ArrayGenerator.generateOrderedArray(n);
            arr3 = Arrays.copyOf(arr2, arr2.length);
            SortingHelper.sortTest("InsertionSort2", arr2);
            SortingHelper.sortTest("SelectionSort", arr3);

            System.out.println();

        }
    }
}
